#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int N = 3e6+10;
const int M = 1e5+10;
const int base = 131;

struct query{
	int l,r,id,bl;
	friend bool operator < (query a,query b){return a.bl ^ b.bl ? a.bl < b.bl : a.bl & 1 ? a.r < b.r : a.r > b.r;}
}q[M];

ll ans[M],now;
int BL,n,m,k,l,r,nodenum;
ull pw[N],hsh[N],id[N],cnt[N];
unordered_map<ull,int> mp;
char s[N];

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in,m = in,k = in; BL = n / sqrt(m);
	for(int i = (pw[0] = 1);i <= n;i++) pw[i] = pw[i-1] * base;
	scanf("%s",s+1);
	for(int i = 1;i <= n;i++) hsh[i] = hsh[i-1] * base + s[i];
	for(int i = 1;i <= n-k+1;i++){
		ull x = hsh[i+k-1] - hsh[i-1] * pw[k];
		if(!mp.count(x)) mp[x] = ++nodenum;
		id[i] = mp[x];
	}
	for(int i = 1;i <= m;i++){
		q[i].l = in,q[i].r = in; q[i].id = i;
		if(q[i].r > n-k+1) q[i].r = n-k+1;
		if(q[i].l > q[i].r) q[i].l = 1,q[i].r = 0;
		q[i].bl = (q[i].l - 1) / BL + 1;
	}
	sort(q+1,q+m+1);l = 1,r = 0;
	for(int i = 1;i <= m;i++){
		while(l < q[i].l) now -= --cnt[id[l++]];
		while(l > q[i].l) now += cnt[id[--l]]++;
		while(r < q[i].r) now += cnt[id[++r]]++;
		while(r > q[i].r) now -= --cnt[id[r--]];
		ans[q[i].id] = now;
	}
	for(int i = 1;i <= m;i++) printf("%lld\n",ans[i]);
	return 0;
}

